package leetcode.editor.cn;

import java.util.Stack;

/**
 * @id: 92
 * @title: 反转链表 II
 */
 
//给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链
//表节点，返回 反转后的链表 。
// 
//
// 示例 1： 
//
// 
//输入：head = [1,2,3,4,5], left = 2, right = 4
//输出：[1,4,3,2,5]
// 
//
// 示例 2： 
//
// 
//输入：head = [5], left = 1, right = 1
//输出：[5]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点数目为 n 
// 1 <= n <= 500 
// -500 <= Node.val <= 500 
// 1 <= left <= right <= n 
// 
//
// 
//
// 进阶： 你可以使用一趟扫描完成反转吗？ 
// Related Topics 链表 
// 👍 785 👎 0

public class P92ReverseLinkedListIi {
    public static void main(String[] args) {
        Solution solution = new P92ReverseLinkedListIi().new Solution();
        // todo
        ListNode head = new ListNode(1,
                new ListNode(2,
                        new ListNode(3,
                                new ListNode(4,
                                        new ListNode(5)))));
//        ListNode head = new ListNode(3, new ListNode(5));
        ListNode result = solution.reverseBetween(head, 2, 4);
        System.out.println(result);
    }
    
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 一次遍历
        ListNode vHead = new ListNode(-1, head);
        ListNode currNode = vHead;
        ListNode preNode = head;
        ListNode nextNode = head.next;
        int index = 0;
        while (currNode != null) {
            if (index == left-1) {
                preNode = currNode;
            }
            if (index == right) {
                break;
            }
            if (left <= index && index <= right) {
                currNode.next = nextNode.next;
                nextNode.next = preNode.next;
                preNode.next = nextNode;
                nextNode = currNode.next;
                index++;
                continue;
            }
            index++;
            currNode = currNode.next;
            if (currNode != null)
                nextNode = currNode.next;
        }
        return vHead.next;
    }


}

//leetcode submit region end(Prohibit modification and deletion)
}
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}